/**
 * @author smallwang
 * @email justdoalitter@gmail.com
 * @create date 2025-02-03 19:40:02
 * @modify date 2025-02-03 19:40:02
 * @desc [description]
 */
package ltd.smallwang;

import ltd.smallwang.common.ListNode;

public class Leetcode0023 {
  public ListNode mergeKLists(ListNode[] lists) {
    return mergeKLists02(lists, 0, lists.length - 1);
  }

  private ListNode mergeKLists02(ListNode[] lists, int begin, int end) {
    if (lists.length == 0) {
      return null;
    }
    if (begin == end) {
      return lists[begin];
    }
    if (end - begin == 1) {
      return mergeTwoList(lists[begin], lists[end]);
    }
    int mid = (begin + end) / 2;
    return mergeTwoList(mergeKLists02(lists, begin, mid), mergeKLists02(lists, mid + 1, end));
  }

  private ListNode mergeTwoList(ListNode list1, ListNode list2) {
    if (list1 == null) {
      return list2;
    }
    if (list2 == null) {
      return list1;
    }
    if (list1.val < list2.val) {
      list1.next = mergeTwoList(list1.next, list2);
      return list1;
    } else {
      list2.next = mergeTwoList(list1, list2.next);
      return list2;
    }
  }

  @SuppressWarnings("unused")
  private ListNode method1(ListNode[] lists) {
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    while (!isAllEmpty(lists)) {
      ListNode minNode = getMinNode(lists);
      cur.next = minNode;
      cur = cur.next;
    }
    return dummy.next;
  }

  private boolean isAllEmpty(ListNode[] lists) {
    for (ListNode item : lists) {
      if (item != null) {
        return false;
      }
    }
    return true;
  }

  private ListNode getMinNode(ListNode[] lists) {
    int result = Integer.MAX_VALUE;
    for (ListNode item : lists) {
      if (item != null && item.val < result) {
        result = item.val;
      }

    }
    for (int i = 0; i < lists.length; i++) {
      if (lists[i] != null && lists[i].val == result) {
        ListNode temp = lists[i];
        lists[i] = lists[i].next;
        return temp;
      }
    }
    return null;
  }
}
